Node-Initiated Byzantine Consensus Without a Common Clock

摘要

The majority of the literature on consensus assumes that protocols arejointly started at all nodes of the distributed system. We show how to removethis problematic assumption in semi-synchronous systems, where messages delaysand relative drifts of local clocks may vary arbitrarily within known bounds.Our framework is self-stabilizing and efficient both in terms of communicationand time; more concretely, compared to a synchronous start in a synchronousmodel of a non-self-stabilizing protocol, we achieve a constant-factor increasein the time and communicated bits to complete an instance, plus an additivecommunication overhead of O(n log n) broadcasted bits per time unit and node.The latter can be further reduced, at an additive increase in time complexity.